1. Field of the Invention
The present invention relates to a fast motion estimation apparatus and method for compressing video image data in real time using a block matching algorithm, and more particularly, to a fast motion estimation apparatus and method in which motion estimation is carried out by detecting a reference block corresponding to a predetermined block of a current frame of video image data from a plurality of blocks of a previous frame of the video image data included in a search range window.
2. Description of the Related Art
In a block matching algorithm, which is a motion estimation method widely used in various video compression technologies, a current frame of video image data is divided into a plurality of reference blocks, a plurality of reference blocks of a previous block of the video image data that match the respective reference blocks of the current frame are detected from a search range window for the previous frame, the displacements of the reference blocks from the previous frame to the current frame are determined as respective corresponding motion vectors, and the motion vectors and differences between pixel values of the reference blocks of the current frame and the reference blocks of the previous frame are transmitted.
A full search algorithm is a type of block matching algorithm. In the full search algorithm, each of a plurality of reference blocks of a current frame is compared with all of a plurality of blocks within a predetermined search region of a previous frame. The full search algorithm provides block matching with high precision and a simple data flow. In addition, the structure of a control circuit used for executing the full search algorithm is relatively simple. However, the full search algorithm requires a considerable amount of computation, especially when the search region becomes large.
In order to solve problems with the full search algorithm, various fast pattern search methods have been suggested. In most conventional fast pattern search methods, a search pattern is determined taking advantage of the characteristics of a distribution of motion vectors, thereby enhancing the speed of motion estimation. Particularly, a conventional adaptive rood search pattern search method is known to provide a higher motion estimation speed with less picture quality deterioration than other conventional fast pattern search methods.
In the conventional adaptive rood search pattern search method, two unit-size rood search patterns are used. The search may be repeatedly carried out using a unit-size rood search pattern, for example, a diamond search pattern, in a refined search stage.
However, in the conventional adaptive rood search pattern search method, when a video sequence includes much movement, the refined search may be trapped in a local minimum, thus deteriorating the quality of pictures.
FIG. 1 is a diagram illustrating the trapping of a final point of search in a local minimum when determining a motion vector using a conventional adaptive rood search pattern search method. Referring to FIG. 1, a first search iteration is carried out near an origin O0 using an initial search pattern (⊙), and a minimal point obtained in the first search iteration is determined as an origin O1 for a second search iteration. Thereafter, the second search iteration is carried out on pixels (□) near the origin O1 using a unit-size rood search pattern. Thereafter, a minimum point obtained in the second search iteration is determined as an origin O2 for a third search iteration, and the third pixel search is carried out on pixels near the origin O2. In the end, the search is trapped in a local minimum (●). In this case, a video sequence may be compressed with large error components, thus deteriorating the quality of pictures provided by a video codec. Thus, it is necessary to develop a motion estimation technique capable of preventing a final point of search from being trapped in a local minimum.